package com.xiyou.week05.sort;

import java.util.Arrays;

/**
 * 215. 数组中的第K个最大元素
 *
 * @ClassName：FindKthLargest
 * @Author：西柚
 * @Date：2022/2/8 3:23 下午
 * @Versiion：1.0
 */
public class FindKthLargest {

    /**
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * <p>
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 输出: 5
     * <p>
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public int findKthLargest2(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSort(int[] arr, int l, int r, int index) {
        if (l >= r) return arr[l];
        int pivot = partition(arr, l, r);
        if (index <= pivot) {
            return quickSort(arr, l, pivot, index);
        } else {
            return quickSort(arr, pivot + 1, r, index);
        }
    }

    private int partition(int[] a, int l, int r) {
        int pivot = l + (int) (Math.random() % (r - l + 1));
        int pivotVal = a[pivot];

        while (l <= r) {
            while (a[l] < pivotVal) l++;
            while (a[r] > pivotVal) r--;
            if (l == r) break;
            if (l < r) {
                int temp = a[l];
                a[l] = a[r];
                a[r] = temp;
                l++;
                r--;
            }
        }
        return r;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};

        FindKthLargest findKthLargest = new FindKthLargest();
        System.out.println(findKthLargest.findKthLargest(nums, 2));
        System.out.println(findKthLargest.findKthLargest2(nums, 2));
    }
}
